
/*
 * Question: Given a binary tree which root is '*rt',
 * and '*p' and '*q' point to a node respectively. Find
 * the common nearest ancestor of them.
 *
 * date: 01/24/2012
 */

#include <iostream>
#include <stack>
#include "bitree.h"
using namespace std;

class bitree : public _bitree<bitree, char>
{
};

struct snode{
    bitree *rt;
    int tag;
};

/*
 * To obtain the pointer of '*p' or '*q' whose key is
 * specified by 'key' in '*rt'. To put all ancestors
 * of '*p' or '*q' in 'stk' by the path.
 */
bitree *locate(bitree *rt, char key, bitree *stk[])
{
    bitree **sp;
    snode n;
    stack<snode> s;

    n.rt = rt; n.tag = 0;
    while (n.rt || !s.empty()){
        if (n.rt){
            if (n.rt->key == key)
                break;
            s.push(n);
            n.rt = n.rt->lchild; n.tag = 0;
        }
        else{
            n = s.top(); s.pop();
            if (n.tag == 0){
                n.tag = 1;
                s.push(n);
                n.rt = n.rt->rchild; n.tag = 0;
            }
            else{
                n.rt = NULL;
            }
        }
    }

    sp = stk;
    while (!s.empty()){
        n = s.top();
        s.pop();
        *stk++ = n.rt;
    }
    *stk = NULL;

    return n.rt; /* If 'n.rt' is NULL, s is definitely empty. */
}

void print_stack(bitree *stk[])
{
    bitree **p = stk;
    while (*p){
        cout << (*p)->key << " ";
        p++;
    }
    cout << endl;
}

/*
 * Match the two pathes of '*p' and '*q' from the root.
 * Find the last mathched node which is the common ancestor
 * of 'p' and 'q'.
 */
bitree *ancestor(bitree *rt, char keyp, char keyq)
{
    bitree *stkp[128], *stkq[128];
    bitree **sp, **sq;
    bitree *p, *q;

    p = locate(rt, keyp, stkp);
    q = locate(rt, keyq, stkq);
    /*
    print_stack(stkp);
    print_stack(stkq);
    */
    if (!p || !q) return NULL;
    /* Here, stkp[] and stkq[] are both not empty. */
    for (sp = stkp; *sp; sp++)
        ;
    for (sq = stkq; *sq; sq++)
        ;
    while (--sp >= stkp && --sq >= stkq)
        if (*sp != *sq)
            break;
    return *++sp;
}

int main()
{
    bitree *rt, *pa;

    bitree_create<bitree, char>(rt, "ex48.txt");
    pa = ancestor(rt, 'E', 'H');
    if (!pa)
        cout << "p or q does not exist." << endl;
    else
        cout << pa->key << endl;
    bitree_destory(rt);

    return 0;
}
